package primalgorithms.dynamicplanning;

public class _02MaxProfit {
    public static int maxProfit(int[] prices) {
        /**
         * 注意该题与另一股票题有很大区别
         * 该题只允许买一次和卖一次；另一题可以买多次和卖多次！！！
         * 所以以下算法不正确
         *
        int len = prices.length;
        if (len < 2){
            return 0;
        }
        int lowIndex = 0,sum = 0;
        for (int highIndex = 1;highIndex < len;highIndex++){
            if (prices[highIndex - 1] < prices[highIndex] && prices[highIndex] > prices[highIndex + 1]){
                sum += prices[highIndex] - prices[lowIndex];
            }else {
                lowIndex = highIndex;
            }
        }
        return sum;
        */
        int len = prices.length;
        if (len < 2){
            return 0;
        }
        /** 效率一般
         *  可以再优化
        int lowIndex = 0,sum = 0;
        for (int i = 1;i < len;i++){
            if (prices[i] < prices[i-1]){
                lowIndex = prices[lowIndex] < prices[i] ? lowIndex : i;
            }else {
                sum = Math.max(sum,prices[i] - prices[lowIndex]);
            }
        }
        */

        int min = prices[0],maxPro = 0;
        for (int i = 0;i < len;i++){
            min = Math.min(min,prices[i]);
            maxPro = Math.max(maxPro,prices[i]-min);
        }
        return maxPro;
    }
}
